package qsc.algorithm.BFS;

import java.util.LinkedList;

/**
 * @auther QiuShangcheng
 * @create 2021/5/5
 */
public class Bfs {
    public static void main(String[] args) {
        // 测试一把图是否创建ok
        char vertex[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};//对应图二中的1,2,3...
        int[][] matrix =
                new int[vertex.length][vertex.length];
//        test1
//        matrix[0] = new int[]{0, 1, 1, 0, 0};
//        matrix[1] = new int[]{1, 0, 1, 1, 1};
//        matrix[2] = new int[]{1, 1, 0, 0, 0};
//        matrix[3] = new int[]{0, 1, 0, 0, 0};
//        matrix[4] = new int[]{0, 1, 0, 0, 0};

//      test2
        matrix[0] = new int[]{0, 1, 1, 0, 0, 0, 0, 0};
        matrix[1] = new int[]{1, 0, 0, 1, 1, 0, 0, 0};
        matrix[2] = new int[]{1, 0, 0, 1, 1, 1, 1, 0};
        matrix[3] = new int[]{0, 1, 0, 0, 1, 0, 0, 1};
        matrix[4] = new int[]{0, 1, 0, 0, 0, 0, 0, 1};
        matrix[5] = new int[]{0, 0, 1, 0, 0, 0, 1, 0};
        matrix[6] = new int[]{0, 0, 1, 0, 0, 1, 0, 0};
        matrix[7] = new int[]{0, 0, 0, 1, 1, 0, 0, 0};

        System.out.println(matrix.length);
        visited = new boolean[vertex.length];
        Graph graph = new Graph(vertex, matrix, vertex.length);
        graph.show();
        doBFS(graph, 0);

    }

    private static LinkedList<Integer> queue = new LinkedList<>();
    //        记录当前位置已被遍历输出或者正在队列
    private static boolean[] visited;

    public static void bfs(Graph graph, int begin) {
//        把当前遍历点输出出来
        System.out.print(" " + graph.getVertex()[begin] + "->");
//        记录当前位置已被遍历输出
        visited[begin] = true;
//        取出存放当前遍历点的邻接点的数组
        int[] curLink = graph.getMatrix()[begin];

//        取出当前未被遍历过的邻接点
        for (int i = 0; i < graph.getVertex().length; i++) {
//            判断当前是否是邻接点以及当前邻接点是否已被遍历或者正在队列中
            if (curLink[i] == 1 && visited[i] == false) {
//                放入队列
                queue.add(i);
//        记录当前位置已被放入队列
                visited[i] = true;
            }
        }

//        但队列为空时表示完全遍历
        while (!queue.isEmpty()) {
//            取出队头，重复执行以上操作
            int head = queue.removeFirst();
            bfs(graph, head);
        }

    }

    public static void doBFS(Graph graph, int begin) {
        bfs(graph, begin);
        //        经过如上步骤，图中可能还有其他顶点未被访问，继续从下一个顶点执行如上操作
        for (int i = 0; i < visited.length; i++) {
            if (visited[i] = false) {
                bfs(graph, i);
            }
        }
    }
}
